We report the discovery by the RXTE PCA of a second transient accreting millisecond pulsar, XTE J1751-305, during regular monitoring observations of the galactic bulge region. The pulsar has a spin frequency of 435 Hz, making it one of the fastest pulsars. The pulsations contain the signature of orbital Doppler modulation, which implies an orbital period of 42 minutes, the shortest orbital period of any known radio or X-ray millisecond pulsar. The mass function, f(sub x) = (1.278 +/- 0.003) x 10 (exp -6) solar mass, yields a minimum mass for the companion of between 0.013 and 0.0017 solar mass depending on the mass of the neutron star. No eclipses were detected. A previous X-ray outburst in June, 1998, was discovered in archival All-Sky Monitor data. Assuming mass transfer in this binary system is driven by gravitational radiation, we constrain the orbital inclination to be in the range 30 deg-85 deg and the companion mass to be 0.013-0.035 solar mass. The companion is most likely a heated helium dwarf. We also present results from the Chandra HRC-S observations which provide the best known position of XTE J1751-305.